package basic.sort.violence;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.violence
 * @since JDK1.8
 *
 * 给定两个长度都为N的数组weights和values，
 * weights[i]和values[i]分别代表 i号物品的重量和价值。
 * 给定一个正数bag，表示一个载重bag的袋子，
 * 你装的物品不能超过这个重量。
 * 返回你能装下最多的价值是多少?
 */
public class Knapsack {

    /**
     * 用剩余空间去装取最大价值的货品
     * @param w 物品的重量
     * @param v 物品的价值
     * @param index 此时的索引
     * @param rest 剩余空间
     * @return 返回最大价值的货品
     */
    private static int rest(int[] w, int[] v, int index, int rest) {
        // 当剩余空间为0时，无法装载，价值返回-1
        if (rest < 0) {
            return -1;
        }
        // 索引已经超出范围，价值返回0
        if (index == w.length) {
            return 0;
        }

        // 本位置不装载
        int noThis = rest(w, v, index + 1, rest);
        // 本位置装载
        int inThis = rest(w, v, index + 1, rest - w[index]);
        // 因为本位置装载的话，有可能会返回-1，所以进行判断
        if (inThis != -1) {
            return Math.max(inThis + v[index], noThis);
        } else {
            return noThis;
        }
    }

    private static int maxValue(int[] w, int[] v, int bag) {
        if (w == null || v == null || w.length != v.length || w.length == 0) {
            return 0;
        }
        // 尝试函数！
        return rest(w, v, 0, bag);
    }

    private static int maxValue1(int[] w, int[] v, int bag) {
        if (w == null || v == null || w.length != v.length || w.length == 0) {
            return 0;
        }

        // 记忆数组
        int[][] dp = new int[w.length + 1][bag + 1];
        // 初始化
        for (int i = 0; i < w.length + 1; i++) {
            for (int j = 0; j < bag + 1; j++) {
                dp[i][j] = -1;
            }
        }

        // 尝试函数！
        return rest1(w, v, 0, bag, dp);
    }

    private static int rest1(int[] w, int[] v, int index, int rest, int[][]dp) {
        // 当剩余空间为0时，无法装载，价值返回-1
        if (rest < 0) {
            return -1;
        }
        // 假如已经保存过该值，直接返回
        if (dp[index][rest] != -1) {
            return dp[index][rest];
        }
        // 索引已经超出范围，价值返回0
        if (index == w.length) {
            return 0;
        }

        // 本位置不装载
        int noThis = rest1(w, v, index + 1, rest, dp);
        // 本位置装载
        int inThis = rest1(w, v, index + 1, rest - w[index], dp);
        // 因为本位置装载的话，有可能会返回-1，所以进行判断
        if (inThis != -1) {
            dp[index][rest] = Math.max(inThis + v[index], noThis);
        } else {
            dp[index][rest] = noThis;
        }

        return dp[index][rest];
    }

    private static int maxValue2(int[] w, int[] v, int bag) {
        if (w == null || v == null || w.length != v.length || w.length == 0) {
            return 0;
        }

        // 记忆数组
        int[][] dp = new int[w.length + 1][bag + 1];

        for (int i = w.length - 1; i >= 0; i--){
            for (int j = bag; j >= 0; j--){
                if (j - w[i] >= 0) {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }

        return dp[0][bag];
    }

    public static void main(String[] args) {
        int[] weights = { 3, 2, 4, 7, 3, 1, 7 };
        int[] values = { 5, 6, 3, 19, 12, 4, 2 };
        int bag = 15;
        System.out.println(maxValue(weights, values, bag));
        System.out.println(maxValue1(weights, values, bag));
        System.out.println(maxValue2(weights, values, bag));
    }
}
